import random, math, sys
import matplotlib.pyplot as plt # 画图
from copy import deepcopy
from tqdm import *  # 进度条
import csv
from array import array
DEBUG = False

sampleSolution = [0, 1, 20, 9, 3, 12, 26, 25, 24, 4, 23, 22, 21, 0, 13, 2, 15, 14, 6, 27, 5, 16, 17, 8, 18, 0, 7, 19,
                  11, 10, 0]

geneNum = 100  # 种群数量
generationNum = 1000  # 迭代次数

CENTER = 0  # 配送中心

HUGE = 9999999
VARY = 0.05  # 变异几率

n = 23  # 客户点数量
k = 6  # 车辆数量
Q = 4  # 额定载重量, t
dis = 999999  # 续航里程, km
costPerKilo = 10  # 油价
epu = 10  # 早到惩罚成本
lpu = 999999  # 晚到惩罚成本
speed = 5  # 速度，km/h



shortest_path_file = open('new_data2.csv', 'r')
shortest_path = csv.reader(shortest_path_file)
shortest_path = list(shortest_path)
points = [49, 22,
17,
14,
21,
12,
19,
5,
1,
13,
18,
3,
7,
6,
8,
9,
19,
1,
22,
17,
12,
2,
24,
13
]
for i0 in range(13, len(points)):
    points[i0] += 24

# 需求量
t = [0]
for i0 in range(n):
    t.append(1)
# 最早到达时间
#eh = [0, 112, 130, 150, 167, 122, 144, 158, 171]
eh = [0,51,
53,
55,
62,
67,
69,
74,
79,
80,
85,
89,
93,
97,
48,
50,
55,
58,
63,
67,
68,
69,
72,
78
]
# 最晚到达时间
lh = [9999]
for i0 in range(1, len(eh)):
    lh.append(eh[i0] + 10)
# 服务时间
h = [0]
for i0 in range(n):
    h.append(3)

class Gene:
    def __init__(self, name='Gene', data=None):
        self.name = name
        self.length = n + 1
        if data is None:
            self.data = self._getGene(self.length)
        else:
            assert(self.length+k == len(data))
            self.data = data
        self.fit, self.dist_loss, self.time_loss  = self.getFit()
        self.chooseProb = 0  # 选择概率

    # randomly choose a gene
    def _generate(self, length):
        data = [i for i in range(1, length)]
        random.shuffle(data)
        data.insert(0, CENTER)
        data.append(CENTER)
        return data

    # insert zeors at proper positions
    def _insertZeros(self, data):
        sum = 0
        newData = []
        for index, pos in enumerate(data):
            sum += t[pos]
            if sum > Q:
                newData.append(CENTER)
                sum = t[pos]
            newData.append(pos)
        return newData

    # return a random gene with proper center assigned
    def _getGene(self, length):
        data = self._generate(length)
        data = self._insertZeros(data)
        return data

    # return fitness
    def getFit(self):
        fit = distCost = timeCost = overloadCost = fuelCost = 0
        dist = []  # from this to next

        # calculate distance
        i = 1
        while i < len(self.data):
            #print(self.data[i], self.data[i-1])
            dist.append(float(shortest_path[points[self.data[i]]][points[self.data[i-1]]]))
            i += 1

        # distance cost
        distCost = sum(dist)
        # time cost
        indx0 = 1
        temp_list = []
        while self.data[indx0] != CENTER:
            temp_list.append(self.data[indx0])
            indx0 += 1
        timeSpent, _ =  get_goods_spend_time(temp_list)
        delay_time = 0
        onece_delay_time = 0
        for i, pos in enumerate(self.data):

            # skip first center
            if i == 0:
                continue
            # new car
            elif pos == CENTER:
                indx = pos + 1
                temp_list = []
                while self.data[indx] != CENTER:
                    temp_list.append(self.data[indx])
                    indx += 1
                timeSpent, _ =  get_goods_spend_time(temp_list)
                #print(onece_delay_time, delay_time)
                onece_delay_time += delay_time
                delay_time = 0

            # update time spent on road
            timeSpent += (dist[i - 1] / speed)
            #print(timeSpent)
            # arrive early
            if timeSpent < eh[pos]:
                timeCost += ((eh[pos] - timeSpent) * epu)
                timeSpent = eh[pos]
            # arrive late
            elif timeSpent > (lh[pos] + delay_time):
                timeCost += ((timeSpent - lh[pos] - delay_time) * lpu)
                delay_time += timeSpent - lh[pos] + 3
            # update time
            timeSpent += h[pos]
        #print(onece_delay_time)
        # overload cost and out of fuel cost
        load = 0
        distAfterCharge = 0
        for i, pos in enumerate(self.data):
            # skip first center
            if i == 0:
                continue
            # charge here
            if pos > n:
                distAfterCharge = 0
            # at center, re-load
            elif pos == CENTER:
                load = 0
                distAfterCharge = 0
            # normal
            else:
                load += t[pos]
                distAfterCharge += dist[i - 1]
                # update load and out of fuel cost
                overloadCost += (HUGE * (load > Q)) * 10000
                fuelCost += (HUGE * (distAfterCharge > dis))
        #print(str(distCost) + ' + ' + str(timeCost) + ' + ' + str(overloadCost) + ' = ' + str(fit))

        fit = distCost + timeCost + overloadCost
        #print(str(distCost) + ' + ' + str(timeCost) + ' + ' + str(overloadCost) + ' = ' + str(fit))
        return 1/fit, distCost, onece_delay_time

    def updateChooseProb(self, sumFit):
        self.chooseProb = self.fit / sumFit

    def moveRandSubPathLeft(self):
        path = random.randrange(k)  # choose a path index
        index = self.data.index(CENTER, path+1) # move to the chosen index
        # move first CENTER
        locToInsert = 0
        self.data.insert(locToInsert, self.data.pop(index))
        index += 1
        locToInsert += 1
        # move data after CENTER
        while self.data[index] != CENTER:
            self.data.insert(locToInsert, self.data.pop(index))
            index += 1
            locToInsert += 1
        assert(self.length+k == len(self.data))

def getSumFit(genes):
    sum = 0
    for gene in genes:
        sum += gene.fit
    return sum


# return a bunch of random genes
def getRandomGenes(size):
    genes = []
    for i in range(size):
        genes.append(Gene("Gene "+str(i)))
    return genes


# 计算适应度和
def getSumFit(genes):
    sumFit = 0
    for gene in genes:
        sumFit += gene.fit
    return sumFit


# 更新选择概率
def updateChooseProb(genes):
    sumFit = getSumFit(genes)
    for gene in genes:
        gene.updateChooseProb(sumFit)


# 计算累计概率
def getSumProb(genes):
    sum = 0
    for gene in genes:
        sum += gene.chooseProb
    return sum


# 选择复制，选择前 1/3
def choose(genes):
    num = int(geneNum/6) * 2    # 选择偶数个，方便下一步交叉
    # sort genes with respect to chooseProb
    key = lambda gene: gene.chooseProb
    genes.sort(reverse=True, key=key)
    # return shuffled top 1/3
    return genes[0:num]


# 交叉一对
def crossPair(gene1, gene2, crossedGenes):
    gene1.moveRandSubPathLeft()
    gene2.moveRandSubPathLeft()
    newGene1 = []
    newGene2 = []
    # copy first paths
    centers = 0
    firstPos1 = 1
    for pos in gene1.data:
        firstPos1 += 1
        centers += (pos == CENTER)
        newGene1.append(pos)
        if centers >= 2:
            break
    centers = 0
    firstPos2 = 1
    for pos in gene2.data:
        firstPos2 += 1
        centers += (pos == CENTER)
        newGene2.append(pos)
        if centers >= 2:
            break
    # copy data not exits in father gene
    for pos in gene2.data:
        if pos not in newGene1:
            newGene1.append(pos)
    for pos in gene1.data:
        if pos not in newGene2:
            newGene2.append(pos)
    # add center at end
    newGene1.append(CENTER)
    newGene2.append(CENTER)
    # 计算适应度最高的
    key = lambda gene: gene.fit
    possible = []
    while 0 in newGene1:
        newGene1.remove(0)
    while 0 in newGene2:
        newGene2.remove(0)
    newGene1.insert(0, CENTER)
    newGene1.insert(len(newGene1), CENTER)
    newGene2.insert(0, CENTER)
    newGene2.insert(len(newGene2), CENTER)

    sum = 0
    newData = []
    for index, pos in enumerate(newGene1):
        sum += t[pos]
        if sum > Q:
            newData.append(CENTER)
            sum = t[pos]
        newData.append(pos)
    newGene = Gene(data=newData.copy())
    possible.append(newGene)
    # while gene1.data[firstPos1] != CENTER:
    #     newGene = newGene1.copy()
    #     newGene.insert(firstPos1, CENTER)
    #     newGene = Gene(data=newGene.copy())
    #     possible.append(newGene)
    #     firstPos1 += 1
    possible.sort(reverse=True, key=key)
    assert(possible)
    crossedGenes.append(possible[0])
    key = lambda gene: gene.fit
    possible = []

    sum = 0
    newData = []
    for index, pos in enumerate(newGene2):
        sum += t[pos]
        if sum > Q:
            newData.append(CENTER)
            sum = t[pos]
        newData.append(pos)
    newGene = Gene(data=newData.copy())
    possible.append(newGene)


    possible.sort(reverse=True, key=key)
    crossedGenes.append(possible[0])


# 交叉
def cross(genes):
    crossedGenes = []
    for i in range(0, len(genes), 2):
        crossPair(genes[i], genes[i+1], crossedGenes)
    return crossedGenes



# 合并
def mergeGenes(genes, crossedGenes):
    # sort genes with respect to chooseProb
    key = lambda gene: gene.chooseProb
    genes.sort(reverse=True, key=key)
    pos = geneNum - 1
    for gene in crossedGenes:
        genes[pos] = gene
        pos -= 1
    return  genes


# 变异一个
def varyOne(gene):
    varyNum = 10
    variedGenes = []
    for i in range(varyNum):
        p1, p2 = random.choices(list(range(1,len(gene.data)-2)), k=2)
        newGene = gene.data.copy()
        newGene[p1], newGene[p2] = newGene[p2], newGene[p1] # 交换
        variedGenes.append(Gene(data=newGene.copy()))
    key = lambda gene: gene.fit
    variedGenes.sort(reverse=True, key=key)
    return variedGenes[0]


# 变异
def vary(genes):
    for index, gene in enumerate(genes):
        # 精英主义，保留前三十
        if index < 30:
            continue
        if random.random() < VARY:
            genes[index] = varyOne(gene)
    return genes

def get_goods_spend_time(mission = []):
    group_a1 = [1, 2, 3, 4]
    group_a2 = [5, 6, 7, 8]
    group_b1 = [9, 10, 11, 12]
    group_b2 = [13, 14, 15, 16]
    group_c1 = [17, 18, 19, 20]
    group_c2 = [21, 22, 23, 24]
    group_a1.reverse()
    group_b1.reverse()
    group_c1.reverse()
    group = []
    group.append(group_a1)
    group.append(group_a2)
    group.append(group_b1)
    group.append(group_b2)
    group.append(group_c1)
    group.append(group_c2)
    #print(group)
    load_time = len(mission) * 3
    for i in range(len(mission)):
        if(mission[i] > 24):
            mission[i] %= 24
    #mission = set(mission)
    order = []
    abc = [0,0,0,0,0,0]
    for i in range(6):
        for m in mission:
            if m in group[i]:
                #print(m , i, group[i].index(m))
                order.append(m)
                abc[i] = max((group[i].index(m)+1) * 40, abc[i])
    length = 0
    if abc[0] != 0 or abc[1] != 0:
        length = abc[0] + abc[1] + 40
    if abc[2] != 0 or abc[3] != 0:
        length += abc[2] + abc[3]
    if abc[4] != 0 or abc[5] != 0:
        length += abc[4] + abc[5]
    length += 50
    time = length / 5 + load_time
    return time, order




if __name__ == "__main__" and not DEBUG:
    f = open('result.log', 'w')
    for count in range(1):
        f.write(str(count))
        f.write('\n')
        genes = getRandomGenes(geneNum) # 初始种群
        # 迭代
        time_loss_list = []
        dist_loss_list = []
        fit_list = []
        for i in tqdm(range(generationNum)):
            updateChooseProb(genes)
            sumProb = getSumProb(genes)
            chosenGenes = choose(deepcopy(genes))   # 选择
            crossedGenes = cross(chosenGenes)   # 交叉
            genes = mergeGenes(genes, crossedGenes) # 复制交叉至子代种群
            genes = vary(genes) # under construction
            key = lambda gene: gene.fit
            temp_genes = genes.copy()
            temp_genes.sort(reverse=True, key=key)
            time_loss_list.append(str(round(temp_genes[0].time_loss, 2))+',')
            dist_loss_list.append(str(round(temp_genes[0].dist_loss, 2))+',')
            fit_list.append(str(temp_genes[0].fit)+',')
            #print('fit:', genes[0].dist_loss,genes[0].time_loss,genes[0].fit, len(genes))
            #print(genes[0].data)
        # sort genes with respect to chooseProb
        key = lambda gene: gene.fit
        genes.sort(reverse=True, key=key)   # 以fit对种群排序
        print('\r\n')
        print('data:', genes[0].data)
        f.writelines(time_loss_list)
        f.write('\n')
        f.writelines(dist_loss_list)
        f.write('\n')
        f.writelines(fit_list)
        f.write('\n')


        res = []
        order_list = ['0,']
        temp_list = genes[0].data.copy()
        car1 = temp_list[1:5]
        car2 = temp_list[6:10]
        car3 = temp_list[11:15]
        car4 = temp_list[16:20]
        car5 = temp_list[21:25]
        car6 = temp_list[26:-1]
        _, car1 = get_goods_spend_time(car1)
        for i2 in range(len(car1)):
            order_list.append(str(car1[i2])+',')
        order_list.append('0,')
        _, car2 = get_goods_spend_time(car2)
        for i2 in range(len(car2)):
            order_list.append(str(car2[i2])+',')
        order_list.append('0,')
        _, car3 = get_goods_spend_time(car3)
        for i2 in range(len(car3)):
            order_list.append(str(car3[i2])+',')
        order_list.append('0,')
        _, car4 = get_goods_spend_time(car4)
        for i2 in range(len(car4)):
            order_list.append(str(car4[i2])+',')
        order_list.append('0,')
        _, car5 = get_goods_spend_time(car5)
        for i2 in range(len(car5)):
            order_list.append(str(car5[i2])+',')
        order_list.append('0,')
        _, car6 = get_goods_spend_time(car6)
        for i2 in range(len(car6)):
            order_list.append(str(car6[i2])+',')
        order_list.append('0,')

        for d in genes[0].data:
            if d == 0:
                res.append('0,')
            else:
                if points[d] > 24:
                    res.append(str(d)+',')
                else:
                    res.append(str(d)+',')
        print('data:', res)
        print('fit:', genes[0].fit)

        f.writelines(res)
        f.write('\n')
        f.writelines(order_list)
        f.write('\n')
        f.write('------------------------------------------------------------\n')
    f.close()

    # print(len(dist_loss), len(delay_time_loss))
    # for i in range(len(dist_loss)):
    #     if i % 100 == 0:
    #         print(dist_loss[i])
    # print("============================================================")
    # for i in range(len(delay_time_loss)):
    #     if i % 100 == 0:
    #         print(delay_time_loss[i])


if DEBUG:
    # print("START")
    # gene = Gene()
    # print(gene.data)
    # gene.moveRandSubPathLeft()
    # print(gene.data)
    #
    #
    # print("FINISH")
    print(get_goods_spend_time([1, 2, 3, 39, 40]))
